COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.cb ABSTRACT SYNTAX
C00006 ENDMK
C⊗;
.cb ABSTRACT SYNTAX

	When we compute with symbolic expressions, whether they be
computer programs, algebraic expressions, or formulas of logic, many
aspects of their representation are irrelevant for theoretical purposes.  For
example, the sum of ⊗a and ⊗b may be written %2a_+_b%1 as in the most
common algebraic notation, (PLUS ⊗a ⊗b) as in LISP, %2+ab%1 in "Polish
notation" or %2ab+%1 in the reverse Polish notation made popular by the
Hewlett-Packard calculators.  Mathematical logicians even represent
expressions by "Goedel numbers" when they want to represent symbolic
computations as numerical computations, One such Goedel numbering would
represent the sum of ⊗a and ⊗b as %22↑a3↑b%1.  Of course, "the sum of ⊗a
and ⊗b" is just another such notation which we have been using to talk
about the others.

	If, for example, we are interested in evaluating sums or in
compiling them, the details of the representation may be irrelevant.  We
need to be able to tell whether an expression is a sum, if so what the
summands are, and we need to be able to make sums from constituent
expressions.

	%2Abstract syntax%1, first described in [McCarthy 1963],
is a way of presenting only the information about a class of
expressions that is relevant to computing with them, omitting
irrelevant detail.  In fact we can describe computations with
expressions using abstract syntax before we even decide on
a final notation.
Later we shall prove a compiler correct without ever
deciding on a particular representation - any %2concrete syntax%1
corresponding to the abstract syntax will do.

Example 1:

	Consider expressions built up from constants and variables
by forming sums and products.

...
analytic and synthetic syntax
the example computation is the elimination of 0 terms from sums,
1 terms from products, replacement of products with a 0 term by
0 and the replacement of single term sums and products by the
terms themselves.

Example 2: Expressions built up from propositional and individual
variables by forming conditional expressions.

the example computation is the removal of conditional expressions
from premisses as done by Boyer and Moore.

Example 3: LISP which is almost trivial

on to McCarthy and Painter